package binaryTree;

/*
 *@description 完全二叉树的节点个数
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_222 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * @description 利用满二叉树的性质计算
     * @author hkfan
     * @time 2025/6/18 10:16
     */
    public int countNodes(TreeNode root) {
        if (root==null){
            return 0;
        }
        int result = check(root);
        if (result!=-1){
            return (1<<result)-1;
        }
        return 1+countNodes(root.left)+countNodes(root.right);
    }

    // 判断是否为满二叉树
    private int check(TreeNode root) {
        int size1=0,size2=0;
        TreeNode temp = root;
        while (temp!=null){
            size1++;
            temp=temp.left;
        }
        temp = root;
        while (temp!=null){
            size2++;
            temp=temp.right;
        }
        return (size1==size2)?size1:-1;
    }

}
